package stu.day39_day.day41;

public class hw2 {

    public int maxProfit(int k, int[] prices) {

        int len = prices.length;
        int[][][] dp = new int[len][k+1][2];

        for (int i=1;i<=k;i++){
            dp[0][i][0] = 0;
            dp[0][i][1] = -prices[0];
        }

        for(int i=1;i<len;i++){
            for (int j=1;j<=k;j++){
                dp[i][j][0] = Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);
                dp[i][j][1] = Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);
            }
        }



        return dp[len-1][k][0];









    }

}
